package sort;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-31
 * Time: 14:54
 */
public class TestQuick {

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //hoare版本
    //基本思路就是
    //1.定义两个指针一个在数组0下标位置，一个在数组最后的位置
    //2.左边选择keyI下标(或者右边)保存起来，右边指针往前面走寻找比keyI小的元素停下来，接着左边指针开始往后走寻找比keyI大的元素停下来
    //3.交换左边指向的元素和右边指向的元素，循环往复，
    //两个指针相遇的位置就是基准位置pos(即pos位置前面的元素都小于array[pos],pos位置后面的元素都大于array[pos])
    //4.最后将keyI与pos位置的元素(即left和right相遇位置)交换，此时这个位置的元素就是基准元素
    //5.然后进行递归【left,pivot-1】 递归【pivot+1,right】

    /**
     * 提出几个问题
     * 1.为啥while循环里面要有left<right这个条件
     * 这里left是左边界，而right是右边界，只需要在这两个边界之间进行操作。
     * 最外面的while写成left>=right根本就不会执行while里面的操作
     * 里面的while写成left>=right同样的也不会执行。
     * 那里面的可不可以不写  答案是不可以的？   那为什么不可以呢？  因为这里如果没有限制条件的话，那right会在left的前面
     * 整体就交错开最终可能就会导致越界
     * 2.array[right]>=array[keyI]为啥这里要取=号
     * 如果没有=号的情况，那么两指针指向的元素相同时，都不会进入里面的两个while循环，直接两个相等的元素进行交换，最终导致死循环
     * 3.为啥右边找大左边找小？
     * 我们主要是寻找一个基准的位置，让这个位置前面的元素都小于这个位置的元素让后面都大于这个位置的元素，
     * 最终我们要让每个位置都符合这个规则这个数组最终就是有序的
     * 4.为啥左边选择keyI，右边要先取寻找，左边先去寻找不可以么？
     * 如果左边选择keyI，左边去寻找，那最后与keyI位置交换的元素就是大于keyI而不是小于keyI的，因为左边总是先走
     * 5.partition这个方法主要是干什么的？？
     * 是快速排序的核心，主要进行单次递归的逻辑，找到第一次的基准位置，好让下面的执行pivot左边的区间和右边的区间同样的
     * 执行这样的操作也就是递归整体就是有序的
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partition1(int[] array,int left,int right){
         //保存基准的下标
        int keyI = left;
        while(left<right){
            //右边找比keyI小的值停下来
            while(left<right&&array[right]>=array[keyI]){
                right--;
            }
            //左边找比keyI小的值停下来
            while(left<right&&array[left]<=array[keyI]){
                left++;
            }
            //都找到了进行交换
            swap(array,left,right);
        }
        //最后left和right相遇那就更新基准元素
        swap(array,keyI,left);
        return left;
    }
    //挖坑法
    public static int partition2(int[] array,int left,int right){
         int keyI = array[left];
         while(left<right){
             //右边寻找比keyI小的元素放到坑里面
             while(left<right&&array[right]>=keyI){
                 right--;
             }
             //放到坑里面去
             array[left] = array[right];
             //此时right不动，移动left寻找比keyI大的元素放到坑里面
             while(left<right&&array[left]<=keyI){
                 left++;
             }
             array[right] = array[left];
         }
         array[left] = keyI;
         return left;
    }
    //前后指针法
    public static int partition(int[] array,int left,int right){
         //cur前面找小遇到小就++prev然后交换
        int prev = left;
        int cur = left+1;
        int pivot = array[left];
        while(cur<=right){
            if(array[cur]<=pivot&& ++prev!=cur){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

    public static void quickSort(int[] array,int left,int right){
        if(left>=right) return;//left-right区间没有值就不需要排序和继续递归下去,如果只有一个值那证明这个区间是有序的不需要排序和继续递归下去
        int mid = partition(array,left,right);
        quickSort(array,left,mid-1);
        quickSort(array,mid+1,right);
    }

    public static void quick(int[] array){
        quickSort(array,0,array.length-1);
    }

    public static void print(int[] array){
        for(int x:array){
            System.out.print(x+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {6,1,2,7,9,3,4,5,10,8};
        System.out.println("排序前：");
        print(array);
        quick(array);
        System.out.println("排序后：");
        print(array);
    }

}
